1. Field of the Invention
The present invention relates to the storage of data in network devices for packet-based data communication systems wherein data is transmitted in data packets that include headers containing address data by means of which packets are switched or routed to their ultimate destinations.
2. Description of Related Art
Address data in data packets fall into two broad categories. A first category is conventionally termed xe2x80x98network addressesxe2x80x99 and relates to the source and intended destination network of a packet. These are xe2x80x98layer 3xe2x80x99 addresses in the customary OSI layering model. A second category is termed xe2x80x98media access controlxe2x80x99 address data, abbreviated to MAC addresses. These addresses, layer 2 addresses in the OSI model, relate to the devices within the communication system and are used by network devices to perform bridging.
Two common network devices are called routers and bridges. They both comprise a multiplicity of ports, a switching function (usually constituted by an application-specific integrated circuit or ASIC) and a forwarding database. The latter is compiled by reading xe2x80x98sourcexe2x80x99 addresses from incoming packets and storing them in a table along with an identification of the respective port on which the packet was received. Such a table is used by a look-up engine to determine a port from which to dispatch a packet having a xe2x80x98destinationxe2x80x99 address corresponding to a xe2x80x98sourcexe2x80x99 address in the table. As will be seen, such xe2x80x98sourcexe2x80x99 and xe2x80x98destinationxe2x80x99 address may be addresses in either of the aforementioned categories.
If the device receives a packet of which the destination address is not in the look-up table (the forwarding database) it is necessary to broadcast the packet so that an acknowledgement from the destination can be used to resolve the address. Since the broadcast of packets consumes substantial bandwidth (i.e. information-carrying capacity) it is known to partition networks into sub-nets or virtual local area networks (VLANs) whereby the broadcast of packets can be limited to one VLAN.
Both bridges and routers customarily include various buffering, contention resolution and flow control functions which are well known to those skilled in the art and which will not be described further herein. Both bridges and routers and related concepts, such as sub-nets, VLAN""s etc, are well described in the prior art, such as WO96/34474, GB-A-2283645, U.S. Pat. No. 5,027,350 and EP-A-0841782.
However, bridges and routers (which terms are used to denote the respective functions, since devices which perform both functions are available) enable somewhat different functions. Routers, as the name implies, are used to look up a route to another network or sub-network. They make a decision which answers the question: xe2x80x98To which network should the packet be sent?xe2x80x99. For this purpose the forwarding database needs to relate an identification of the subnet, via a network address sometimes termed VLAN address, and an identification, conveniently termed a port mask, of the port to which the sub-net is directly or indirectly connected. In general, a router does not need knowledge of an end station address in its forwarding database. If however a router has to direct a packet to an end station in a directly connected sub-net the router needs to map the network address of the end station to its MAC address, and to place the MAC address on the packet as the packet leaves the router. To enable this mapping, the router has recourse to a table known as an ARP (address resolution protocol) cache, by means of which a record is maintained of mappings between network addresses, such as IP (internet protocol) addresses, and media access control addresses.
Where a routing table constitutes an end station cache (in particular to achieve fast look-up) the storage space required is X(m+i+v+p), where X is the maximum number of entries in the table, m is the number of bits in an MAC address, i is the number of bits in a network or IP address, v is the number of bits in VLAN address, and p is the number of bits in a port mask. Typically, m=48, i=32, v=5 and p=32. The storage capacity required of an ARP cache is X(m+i), the symbols in this expression having the meanings already indicated.
A bridge is used to connect one LAN to another, so that users connected to different LANs can communicate as if they were on the same LAN. For this purpose the bridge merely switches packets from one port to another. It responds to a MAC address and a VLAN address to look up the relevant port mask.
It is customary (as described in for example EP-A-0365337) to include in a bridging table an xe2x80x98agexe2x80x99 field which is constituted by the value of an artificial age at the time the entry was made. The artificial age may be changed from time to time in an alternating or cyclic sequence. The interval between changes may be selected or adapted to the data traffic flow. The age field enables the clearing of unwanted xe2x80x98oldxe2x80x99 entries from the table in a single operation, the entries which have an age field not corresponding to a current age being removed from the table.
The storage required for a bridging table is X(m+v+p+a) where X, m, v, and p relate to the number of entries, the MAC address, the VLAN address and the port mask respectively. The age field a may be one or two bits.
The present invention is particularly concerned with the management of data storage for a device which can function both as a router and a bridge. It may be seen from the foregoing that a simple combination of the ordinary functions of a router and bridge would require data storage corresponding to X(3m+2i+2v+2p+a), both bridges and routers require for their operation response to MAC addresses and in addition a router needs to map between network addresses and MAC addresses.
The basis of the present invention is the use of an address cache which is based on network addresses of end stations. An address cache thus organised may be constituted by a single data table and will, as the following indicates, greatly reduce the storage requirements for separate routing and bridging functions.
In order to access such an xe2x80x98integratedxe2x80x99 cache, the device needs to be able to respond to both MAC (layer 2) addresses and network (layer 3) addresses and a further aspect of the invention is a process which enables the device to act in such a manner.